package sort

import (
	"fmt"
	"math/rand"
	"time"
)

func quickSort(arr []int, start int, end int) {
	if start >= end {
		return
	}
	low, high := start, end
	//随机个位置作为基数
	r := rand.New(rand.NewSource(time.Now().UnixNano()))
	random := r.Intn(end-start) + start
	//设置基数
	Swap(arr, start, random)
	p := arr[start]
	//fmt.Printf("\n开始---- low ：%d，high：%d，base：%d\n", low, high, p)
	for low <= high {
		for low <= high && arr[low] <= p {
			low++
		}

		for low <= high && arr[high] >= p {
			high--
		}
		//fmt.Printf("mid low ：%d，high：%d，base：%d\n", low, high, p)

		if low < high {
			//fmt.Println("交换前", low, high, arr)
			Swap(arr, low, high)
			//fmt.Println("交换后", low, high, arr)
		} else {
			break
		}
	}
	//fmt.Printf("结束前 low ：%d，high：%d， %+v\n", low, high, arr)
	Swap(arr, start, low-1)
	//fmt.Printf("交换 %d -> %d 后， %+v\n", start, low-1, arr)

	quickSort(arr, start, low-2)
	quickSort(arr, low, end)
}

func quickSort2(arr []int, start int, end int) {
	if start >= end {
		return
	}
	q := partition(arr, start, end)
	fmt.Println(q, arr)
	quickSort2(arr, start, q-1)
	quickSort2(arr, q+1, end)
}

func partition(arr []int, start int, end int) int {
	pivot := arr[end]
	fmt.Println("pivot：", pivot)
	i := start
	for j := start; j < end; j++ {
		fmt.Println("i, j ", i, j)
		if arr[j] < pivot {
			if i != j {
				fmt.Println("交换", i, j)
				Swap(arr, i, j)
			}
			i++
		}
	}
	arr[i], arr[end] = pivot, arr[i]
	return i
}

func quick2(arr []int, start int, end int) {
	if start >= end {
		return
	}
	l, r := start, end
	p := arr[end]
	fmt.Println("p = ", p)
	for l <= r {
		if arr[l] < p {
			l++
		}
		if arr[r] > p {
			r--
		}
		if l <= r {
			Swap(arr, l, r)
			l++
			r--
		}
	}
	fmt.Println(arr)
}
